Aufgabe - ggT(2^{n} - 1, 2^{m} - 1) = 2^{ggT(n, m)} - 1

• Involvierte Definitionen:
  • ggT
  • Definition - Vollständige Induktion
  • Teilbarkeit
• Veranstaltung: AlMa
• Referenz:

⠀

Aufgabe

Für alle gilt:

Anmerkung

Eine leicht veränderte Version hiervon findet sich auch in AlMa EA1.1

Beweis

Seien . Wir zeigen die Behauptung per Induktion nach , wobei .

Induktionsanfang

Sei , also . Dann gilt:

Damit hält der Induktionsanfang.

Induktionsvoraussetzung

Sei beliebig, aber fest.
Für alle mit gelte:

Die Sonderbedingung (siehe auch starke Induktion), dass für alle mit gilt, werden wir beim Einsetzen der Induktionsvoraussetzung benötigen.

Induktionsschritt

Wir führen die Induktion von , wobei wir voraussetzen, dass . Es ist also zu zeigen, dass:

beziehungsweise

Im Folgenden werden wir bloß Gleichung zeigen. Gleichung folgt jedoch direkt durch entsprechende Umbenennung von und in Kombination mit der Kommutativität des ggT.

O.b.d.A nehmen wir weiter an, dass . Bei Beweisen über den ggT sind in der Regel (und so auch hier) zwei Fälle zu betrachten:

1. teilt
2. teilt nicht

Betrachten wir zunächst den ersten Fall:

1. Fall: teilt

In einem früheren Satz haben wir bereits gezeigt:

Da nach Voraussetzung dieses Falls ist, wissen für die rechte Seite von Gleichung also schon, dass:

Damit Gleichung gilt, ist nun noch zu zeigen, dass

In anderen Worten: wir müssen zeigen, dass ein Teiler von ist. Unter Zuhilfenahme von Gleichung folgt diese Aussage dann nämlich direkt.

Hierzu untersuchen wir die Definition der Teilbarkeit genauer. Dass ein Teiler von ist (die Voraussetzung für diesen Fall), bedeutet, dass es ein gibt, sodass

Damit können wir auch schreiben als:

Gleichung zeigt uns genau, was wir wissen wollten, nämlich dass ein Teiler von ist.

Mit den beiden Gleichungen und folgt damit, was wir schon in Gleichung vermutet haben. Hier noch einmal ausgeschrieben:

Wir erhalten also:

Damit hält Fall 1.

2. Fall: teilt nicht

Da kein Teiler von , können wir den Fall ausschließen. Es gilt also:

Damit können wir auch schreiben als:

Das heißt, es gilt:

Wobei besagt:

Kann man nicht einfach zeigen, dass ?

Nun, man kann, wie in Gleichung , zeigen, dass .

Leider können wir hier nicht die Eigenschaft des ggT anwenden, die wir in Gleichung genutzt haben. In der Regel ist , das ist aber eine Voraussetzung für diese Regel.

Eine Auflistung der möglichen natürlichzahligen Ergebnisse findet sich hier (jedenfalls bis WolframAlpha wieder die Syntax ändert).

Da wir vorausgesetzt haben, dass , gilt für die Exponenten aus Gleichung :

Gleichung zeigt, dass der Induktionsvoraussetzung entspricht. Damit gilt weiter:

was zu zeigen war. Wobei besagt:

Damit halten sowohl Fall 1 und Fall 2, womit wir fertig sind.